/*Copyright (C) 2013-2020 LZE*/
#include<bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;
typedef long long ll;
const int N=500010;
const int M=500010;
int n,m,s,tot,nbs[N],dis[N],heap[N],ptr[N],str[N];
struct Edge {
	int ed;
	int next;
	int v;
} edge[M];
bool b[N];
void init(){
	int u,v,w;
	cin>>n>>m>>s;
	tot = 0;
	for (int i=1;i<=m;i++){
		cin>>u>>v>>w;
		tot++;
		edge[tot].ed=v; edge[tot].v=w; edge[tot].next=nbs[u]; nbs[u]=tot;
	}
}
void dijkstra(){
	for (int i=0;i<=n;i++)
		dis[i]=INF;
	dis[s]=0;
	for (int i=1;i<=n;i++)
	{
		int k=0;
		for (int j=1;j<=n;j++)
			if (!b[j] && dis[j]<dis[k]) k=j;
		b[k]=1;
		int j=nbs[k];
		while (j!=0){
			if (!b[edge[j].ed] && dis[k]+edge[j].v<dis[edge[j].ed]){
				dis[edge[j].ed]=dis[k]+edge[j].v;
			}
			j=edge[j].next;
		}
	}
}
int main(){
	init();
	dijkstra();
	for (int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}